1. Field of the Invention
The present invention relates generally to apparatus and a technique for sorting and, in particular, to a bubble sorting technique implemented in a serial chain of sorting modules.
2. Description of the Prior Art
Since "virtually every important aspect of programming arises somewhere in the context of sorting or searching" (D. E. Knuth, The Art of Computer Programming, Vol. III, Addison-Wesley, 1973), the subject has been widely studied both by computer scientists as well as electronics hardware designers, and numerous techniques including selection sort, heap sort, insertion sort and merge sort have been described in the literature. Yet another technique, called "bubble sorting", is also very popular, and even this one technique has been known by several names, including interchange sorting, exchange sorting and sinking sort. Despite this diversity in nomenclature, it is generally agreed that the essence of a bubble sort is the interchange of two adjacent items in the batch being sorted. During each interchange, the values of the items are compared, and the items are rearranged if necessary, so as to put them in a predetermined relationship, eg, smallest first or largest first. The interchanges are typically performed sequentially, generally by repeatedly scanning or traversing all items in the batch until no further interchanges have been made, at which time the entire batch has been sorted as desired. Many of the bubble sort techniques are software implemented (see, eg, Popular Computing, Vol. 8, No. 11, November 1980, "Bubble Sorting", pp. 2-10) and thus must essentially be limited to a series of sequential operations, since most general purpose computers include only one processor. To overcome resultant processing speed limitations, various hardware implementations have been devised for bubble sorting, using conventional integrated circuit technology and magnetic bubble domain devices. An example of the latter is described in an article by D. T. Lee et al entitled "An On-Chip Compare/Steer Bubble Sorter", IEEE Trans. on Computers, Vol. C-30, No. 6, June 1981, pp. 396-405 (see particularly FIG. 6), while an IC implementation is described in an article by P. G. Jansen et al entitled "The DIMOND: A Component for the Modulator Construction of Switching Networks", IEEE Trans. on Computers, Vol. C-29, No. 10, October 1980, pp. 884-889 (see particularly FIG. 8).
The effectiveness of any of the prior art bubble sorting arrangements must be measured against a large number of factors, such as the available throughput and latency as well as the required memory size. Ideally, the apparatus should be flexible in terms of the number of items that can be sorted in each batch and the design be amenable to modular fabrication using VLSI technology. Many of the known sorting arrangements which have been successful in improving performance in terms of some of the above criteria have nevertheless been costly or difficult to implement.
In view of the foregoing, it is the broad object of the present invention to provide a sorting technique which is efficient in terms of latency, throughput and memory requirements, and which can be implemented in a modular arrangement suitable for VLSI fabrication. In particular, it is important that flexibility be maintained, so that the number of items in each batch to be sorted can be reasonably varied.